package datastructure.queue2;

import java.util.Iterator;

/**
 * 单向循环链表带哨兵实现队列
 *
 * @author 杨 强
 * @package datastructure.queue2
 * @createTime 2023-03-13 21:16
 */
public class LinkedListQueue<E> implements Queue<E>, Iterable<E> {

    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        // 添加3个元素
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        // 打印队列
        Iterator<Integer> iterator = queue.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        // 移除一个
        Integer poll = queue.poll();
        System.out.println("移除了" + poll);
        // 打印队列
        Iterator<Integer> iterator1 = queue.iterator();
        while (iterator1.hasNext()){
            System.out.println(iterator1.next());
        }
    }

    /**
     * 定义节点类
     * @param <E> 节点的数据类型
     */
    private static class Node<E>{
        E value;
        Node<E> next;
        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 队列的节点数量
     */
    private int size;
    /**
     * 队列的容量大小, 不知道就int最大值,指定就是指定的值
     */
    private int capacity = Integer.MAX_VALUE;
    /**
     * 头节点
     */
    private Node<E> head =  new Node<>(null, null);
    /**
     * 尾节点和头结点是同一个节点
     */
    private Node<E> tail = head;
    /**
     * 代码块:
     *      初始化单向循环带哨兵的链表
     *      哨兵作为头尾节点,然后自己自己指向自己,尾节点指向头节点
     */
    {
        tail.next = head;
    }

    /**
     * 有参构造, 设置队列的容量
     * @param capacity 队列容量
     */
    public LinkedListQueue(int capacity) {
        this.capacity = capacity;
    }
    /**
     * 无参构造
     */
    public LinkedListQueue() {
    }

    @Override
    public boolean offer(E value) {
        // 判断容量
        if (isFull()){
            return false;
        }
        // 创建新节点, 新节点作为尾节点,下一个节点指向的就是哨兵头节点
        Node<E> addNode = new Node<>(value, head);
        // 指针变化, 看图会很明白
        tail.next = addNode; // 这一步是为了指针链不断开
        tail = addNode;
        // 队列数量加一
        size++;
        return true;
    }

    @Override
    public E poll() {
        // 判断队列是否为空
        if (isEmpty()){
            return null;
        }
        // 获取头节点
        Node<E> first = head.next;
        // 指针变化, 就是移除该节点
        head.next = first.next;
        // 如果获取的是最后一个节点, 那么就头节点等于尾节点, 就等于初始化了链表队列
        if (first == tail){
            head = tail;
        }
        // 容量减一
        size--;
        return first.value;
    }

    @Override
    public E peek() {
        // 判断队列是否为空
        if (isEmpty()){
            return null;
        }
        // 获取头节点的值
        return head.next.value;
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        return this.size == this.capacity;
    }


    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            // 遍历的时候直接获取下一个节点,因为头节点是哨兵节点
            Node<E> p = head.next;
            @Override
            public boolean hasNext() {
                // 如果节点的下一个节点是头节点,那么就到了哨兵节点, 就结束循环
                return p != head;
            }
            @Override
            public E next() {
                // 获取当前节点的值,并且执行下一个节点
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}
